package com.mdnote.algorithm;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/8
 * @description 动态规划 —— 背包问题
 */
public class KnapsakProblem {

    public static void main(String[] args) {
        KnapsakProblem knapsakProblem = new KnapsakProblem();
        int[] weights = {1, 4, 3};
        int[] prices = {1500, 3000, 2000};
        knapsakProblem.pack(weights, prices, 4);
    }

    /**
     * 背包问题
     * @param weights 重量
     * @param prices 价格
     * @param totalWeight 背包最大容量
     */
    private void pack(int[] weights, int[] prices, int totalWeight) {
        // 维护一个二维数组，二维数组中的每一个值都对应着最优解，下一步的最优解需要参考上一层的两个最优解（一个是不放入，另一个是放入）
        // arr的value代表最大价值
        int[][] arr = new int[weights.length + 1][totalWeight + 1];
        // 用于记录添加顺序
        int[][] path = new int[weights.length + 1][totalWeight + 1];
        // 初始化一下这个数组
        for (int i = 0; i < arr.length; i++) {
            arr[i][0] = 0;
        }
        for (int i = 0; i < arr[0].length; i++) {
            arr[0][i] = 0;
        }

        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < arr[0].length; j++) {
                // i 表示物品， j 表示当前的背包容量
                // 如果当前的物品比背包容量大，放不下，直接使用之前的数据
                if (weights[i - 1] > j) {
                    arr[i][j] = arr[i - 1][j];
                } else {
                    // prices[i] + arr[i - 1][j - weights[i - 1]中
                    //  arr[i - 1][j - weights[i - 1]表示的是在没加入当前商品时的最优解
                    // prices[i] + arr[i - 1][j - weights[i - 1]] 可以理解成未加入该商品时的，当前容量减去商品容量所对应的最优解
                    if (arr[i - 1][j] < prices[i - 1] + arr[i - 1][j - weights[i - 1]]) {
                        // 添加新物品
                        arr[i][j] = prices[i - 1] + arr[i - 1][j - weights[i - 1]];
                        // 记录当前的添加记录
                        path[i][j] = 1;
                    } else {
                        // 不添加新物品，沿用上次的最优解
                        arr[i][j] = arr[i - 1][j];
                    }
                }

            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(Arrays.toString(arr[i]));
        }


        // 现在最优解就在数组的右下角，我们怎么知道这个球最优解的过程呢
        // 最优解是依靠上一次（i - 1）的最优解
        for (int i = 0; i < path.length; i++) {
            for (int j = 0; j < path[0].length; j++) {
               if (path[i][j] == 1) {
                   System.out.println( i +" " + j);
               }
            }
        }
        int i = path.length - 1;
        int j = path[0].length - 1;
        while (i > 0 && j > 0) {
            if (path[i][j] == 1) {
                System.out.println("将物品" + i + "放入背包中");
                j = j - weights[i - 1];
            }
            i--;
        }
    }
}
